// @test([1])=[[1]]
// @algorithm @lc id=1000010 lang=javascript
// @title bst-sequences-lcci
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

function mergeSeq(l, lIdx, r, rIdx, buff, ans) {
  // 如果左右子树的序列都选择过了，表示一个组合完成，将结果放入答案中
  if (lIdx === l.length && rIdx === r.length) {
    ans.push([...buff]);
    return ans;
  }
  // 左边取一个放入组合中，递归
  if (lIdx < l.length) {
    buff.push(l[lIdx]);
    mergeSeq(l, lIdx + 1, r, rIdx, buff, ans);
    buff.pop();
  }
  // 右边取一个放入组合中，递归
  if (rIdx < r.length) {
    buff.push(r[rIdx]);
    mergeSeq(l, lIdx, r, rIdx + 1, buff, ans);
    buff.pop();
  }
}
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var BSTSequences = function (root) {
  const ans = [];
  if (root === null) {
    ans.push([]);
    return ans;
  }
  // 左右字数的序列集合
  const lSeq = BSTSequences(root.left);
  const rSeq = BSTSequences(root.right);

  for (const l of lSeq) {
    for (const r of rSeq) {
      const buff = [root.val];
      // 将左右子树的序列做一次排列组合，放入结果
      mergeSeq(l, 0, r, 0, buff, ans);
    }
  }

  return ans;
};
